#include "clib_container_double_ended_vector.h"


struct clib_container_double_ended_vector {
    size_t size;
    size_t capacity;
    size_t first;
    size_t last;
    void **buffer;

    void *(*mem_malloc_func)(size_t size);

    void (*mem_free_func)(void *block);

    void *(*mem_copy_func)(void *target, void *src, size_t size);
};

int clib_container_double_ended_vector_new_conf(struct clib_container_double_ended_vector_conf const *const conf,
                                                struct clib_container_double_ended_vector **vector) {
    struct clib_container_double_ended_vector *deque = conf->mem_malloc_func(
            sizeof(struct clib_container_double_ended_vector));
    if (!deque) {
        return CLIB_RES_MEMORY_ERROR;
    }
    if (!(deque->buffer = conf->mem_malloc_func(conf->capacity * sizeof(void *)))) {
        conf->mem_free_func(deque);
        return CLIB_RES_MEMORY_ERROR;
    }
    deque->mem_malloc_func = conf->mem_malloc_func;
    deque->mem_free_func = conf->mem_free_func;
    deque->mem_copy_func = conf->mem_copy_func;
    deque->capacity = clib_align_pow2(conf->capacity);
    deque->first = 0;
    deque->size = 0;
    *vector = deque;
    return CLIB_RES_OK;
}


void clib_container_double_ended_vector_destroy(struct clib_container_double_ended_vector *vector) {
    vector->mem_free_func(vector->buffer);
    vector->mem_free_func(vector);
}

static void
copy_buffer(struct clib_container_double_ended_vector const *const vector, void **buff) {
    if (vector->last > vector->first) {
        vector->mem_copy_func(buff,
                              &(vector->buffer[vector->first]),
                              vector->size * sizeof(void *));
    } else {
        size_t l = vector->last;
        size_t e = vector->capacity - vector->first;

        vector->mem_copy_func(buff,
                              &(vector->buffer[vector->first]),
                              e * sizeof(void *));

        vector->mem_copy_func(&(buff[e]),
                              vector->buffer,
                              l * sizeof(void *));
    }
}

static int expand_capacity(struct clib_container_double_ended_vector *vector) {
    if (vector->capacity == UINT32_MAX) {
        return CLIB_RES_MEMORY_ERROR;
    }
    size_t new_capacity = vector->capacity << 1;
    void **new_buffer = vector->mem_malloc_func(new_capacity * sizeof(void *));
    if (!new_buffer) {
        return CLIB_RES_MEMORY_ERROR;
    }
    copy_buffer(vector, new_buffer);
    vector->mem_free_func(vector->buffer);

    vector->first = 0;
    vector->last = vector->size;
    vector->capacity = new_capacity;
    vector->buffer = new_buffer;

    return CLIB_RES_OK;
}


int clib_container_double_ended_vector_add_last(struct clib_container_double_ended_vector *vector, void *element) {
    if (vector->capacity == vector->size && expand_capacity(vector) != CLIB_RES_OK) {
        return CLIB_RES_MEMORY_ERROR;
    }
    vector->buffer[vector->last] = element;
    vector->last = (vector->last + 1) & (vector->capacity - 1);
    vector->size++;
    return CLIB_RES_OK;
}

int clib_container_double_ended_vector_add_first(struct clib_container_double_ended_vector *vector, void *element) {
    if (vector->size >= vector->capacity && expand_capacity(vector) != CLIB_RES_OK) {
        return CLIB_RES_MEMORY_ERROR;
    }
    vector->first = (vector->first - 1) & (vector->capacity - 1);
    vector->buffer[vector->first] = element;
    vector->size++;
    return CLIB_RES_OK;
}

int clib_container_double_ended_vector_add(struct clib_container_double_ended_vector *vector, void *element) {
    return clib_container_double_ended_vector_add_last(vector, element);
}

int clib_container_double_ended_vector_add_with_index(struct clib_container_double_ended_vector *vector,
                                                      void *element, size_t index) {
    if (index >= vector->size) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    if (vector->capacity == vector->size && expand_capacity(vector) != CLIB_RES_OK) {
        return CLIB_RES_MEMORY_ERROR;
    }
    const size_t max_index = vector->capacity - 1;
    const size_t l = vector->last & max_index;
    const size_t f = vector->first & max_index;
    const size_t p = (vector->first + index) & max_index;
    if (index == 0) {
        //添加到第一个元素
        return clib_container_double_ended_vector_add_first(vector, element);
    }
    if (index == max_index) {
        //添加到最后一个元素
        return clib_container_double_ended_vector_add_last(vector, element);
    }
    if (index <= (vector->size / 2) - 1) {
        if (p < f || f == 0) {
            const size_t r_move = (f != 0) ? max_index - f + 1 : 0;
            const size_t l_move = p;
            void *e_first = vector->buffer[0];
            if (f != 0) {
                memmove(&(vector->buffer[f - 1]),
                        &(vector->buffer[f]),
                        r_move * sizeof(void *));
            }
            if (p != 0) {
                memmove(&(vector->buffer[0]),
                        &(vector->buffer[1]),
                        l_move * sizeof(void *));
            }
            vector->buffer[max_index] = e_first;
        } else {
            memmove(&(vector->buffer[f - 1]),
                    &(vector->buffer[f]),
                    index * sizeof(void *));
        }
        vector->first = (vector->first - 1) & max_index;
    } else {
        if (p > l || l == max_index) {
            void *e_last = vector->buffer[max_index];
            if (p != max_index) {
                memmove(&(vector->buffer[p + 1]),
                        &(vector->buffer[p]),
                        (max_index - p) * sizeof(void *));
            }
            if (l != max_index) {
                memmove(&(vector->buffer[1]),
                        &(vector->buffer[0]),
                        (l + 1) * sizeof(void *));
            }
            vector->buffer[0] = e_last;
        } else {
            memmove(&(vector->buffer[p + 1]),
                    &(vector->buffer[p]),
                    (vector->size - index) * sizeof(void *));
        }
        vector->last = (vector->last + 1) & max_index;
    }
    vector->buffer[p] = element;
    vector->size++;
    return CLIB_RES_OK;
}

int
clib_container_double_ended_vector_replace_with_index(struct clib_container_double_ended_vector *vector, void *element,
                                                      size_t index, void **out) {
    if (index >= vector->size) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    size_t i = (vector->first + index) & (vector->capacity - 1);
    if (out) {
        *out = vector->buffer[i];
    }
    vector->buffer[i] = element;
    return CLIB_RES_OK;
}

int clib_container_double_ended_vector_index_of(struct clib_container_double_ended_vector const *const vector,
                                                const void *element, size_t *index) {
    size_t i;
    for (i = 0; i < vector->size; i++) {
        size_t p = (vector->first + i) & (vector->capacity - 1);
        if (vector->buffer[p] == element) {
            *index = i;
            return CLIB_RES_OK;
        }
    }
    return CLIB_RES_OUT_OF_BOUNDS_ERROR;
}

int clib_container_double_ended_vector_remove_first(struct clib_container_double_ended_vector *vector, void **out) {
    if (vector->size == 0) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    void *element = vector->buffer[vector->first];
    vector->first = (vector->first + 1) & (vector->capacity - 1);
    vector->size--;

    if (out) {
        *out = element;
    }
    return CLIB_RES_OK;
}

int clib_container_double_ended_vector_remove_last(struct clib_container_double_ended_vector *vector,
                                                   void **out) {
    if (vector->size == 0) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    size_t last = (vector->last - 1) & (vector->capacity - 1);
    void *element = vector->buffer[last];
    vector->last = last;
    vector->size--;

    if (out) {
        *out = element;
    }
    return CLIB_RES_OK;
}


int
clib_container_double_ended_vector_remove_with_index(struct clib_container_double_ended_vector *vector, size_t index,
                                                     void **out) {
    if (index >= vector->size) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    const size_t c = vector->capacity - 1;
    const size_t l = vector->last & c;
    const size_t f = vector->first & c;
    const size_t p = (vector->first + index) & c;

    void *removed = vector->buffer[index];

    if (index == 0) {
        return clib_container_double_ended_vector_remove_first(vector, out);
    }
    if (index == c) {
        return clib_container_double_ended_vector_remove_last(vector, out);
    }

    if (index <= (vector->size / 2) - 1) {
        if (p < f) {
            void *e = vector->buffer[c];

            if (f != c) {
                memmove(&(vector->buffer[f + 1]),
                        &(vector->buffer[f]),
                        (c - f) * sizeof(void *));
            }
            if (p != 0) {
                memmove(&(vector->buffer[1]),
                        &(vector->buffer[0]),
                        p * sizeof(void *));
            }
            vector->buffer[0] = e;
        } else {
            memmove(&(vector->buffer[f + 1]),
                    &(vector->buffer[f]),
                    index * sizeof(void *));
        }
        vector->first = (vector->first + 1) & c;
    } else {
        if (p > l) {
            void *e = vector->buffer[0];

            if (p != c) {
                memmove(&(vector->buffer[p]),
                        &(vector->buffer[p + 1]),
                        (c - p) * sizeof(void *));
            }
            if (p != 0) {
                memmove(&(vector->buffer[1]),
                        &(vector->buffer[0]),
                        l * sizeof(void *));
            }
            vector->buffer[c] = e;
        } else {
            memmove(&(vector->buffer[p]),
                    &(vector->buffer[p + 1]),
                    (l - p) * sizeof(void *));
        }
        vector->last = (vector->last - 1) & c;
    }
    vector->size--;

    if (out) {
        *out = removed;
    }
    return CLIB_RES_OK;
}


int clib_container_double_ended_vector_remove(struct clib_container_double_ended_vector *vector,
                                              void *element, void **out) {
    size_t index;
    int status = clib_container_double_ended_vector_index_of(vector, element, &index);

    if (status != CLIB_RES_OK) {
        return status;
    }
    return clib_container_double_ended_vector_remove_with_index(vector, index, out);
}

int
clib_container_double_ended_vector_get_with_index(struct clib_container_double_ended_vector const *const vector,
                                                  size_t index,
                                                  void **out) {
    if (index > vector->size) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    size_t i = (vector->first + index) & (vector->capacity - 1);
    *out = vector->buffer[i];
    return CLIB_RES_OK;
}

int clib_container_double_ended_vector_get_first(struct clib_container_double_ended_vector const *const vector,
                                                 void **out) {
    if (vector->size == 0) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    *out = vector->buffer[vector->first];
    return CLIB_RES_OK;
}

int
clib_container_double_ended_vector_get_last(struct clib_container_double_ended_vector const *const vector, void **out) {
    if (vector->size == 0) {
        return CLIB_RES_OUT_OF_BOUNDS_ERROR;
    }
    size_t last = (vector->last - 1) & (vector->capacity - 1);
    *out = vector->buffer[last];
    return CLIB_RES_OK;
}

int clib_container_double_ended_vector_trim_capacity(struct clib_container_double_ended_vector *vector) {
    if (vector->capacity == vector->size) {
        return CLIB_RES_OK;
    }
    size_t new_size = clib_align_pow2(vector->size);
    if (new_size == vector->capacity) {
        return CLIB_RES_OK;
    }
    void **new_buff = vector->mem_malloc_func(sizeof(void *) * new_size);
    if (!new_buff) {
        return CLIB_RES_MEMORY_ERROR;
    }
    copy_buffer(vector, new_buff);
    vector->mem_free_func(vector->buffer);

    vector->buffer = new_buff;
    vector->first = 0;
    vector->last = vector->size;
    vector->capacity = new_size;
    return CLIB_RES_OK;
}

void clib_container_double_ended_vector_reverse(struct clib_container_double_ended_vector *vector) {
    size_t i;
    size_t j;
    size_t s = vector->size;
    size_t c = vector->capacity - 1;
    size_t first = vector->first;
    for (i = 0, j = s - 1; i < (s - 1) / 2; i++, j--) {
        size_t f = (first + i) & c;
        size_t l = (first + j) & c;

        void *tmp = vector->buffer[f];
        vector->buffer[f] = vector->buffer[l];
        vector->buffer[l] = tmp;
    }
}


size_t clib_container_double_ended_vector_contains(struct clib_container_double_ended_vector const *const vector,
                                                   const void *element) {
    size_t i;
    size_t o = 0;
    for (i = 0; i < vector->size; i++) {
        size_t p = (vector->first + i) & (vector->capacity - 1);
        if (vector->buffer[p] == element)
            o++;
    }
    return o;
}

size_t clib_container_double_ended_vector_get_current_size(struct clib_container_double_ended_vector const *const vector) {
    return vector->size;
}

size_t clib_container_double_ended_vector_get_capacity(struct clib_container_double_ended_vector const *const vector) {
    return vector->capacity;
}